package ar.uba.fi.tonyvaliente.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class InnerBPlusTreeNode<K extends Comparable<K>, V> extends BPlusTreeNode<K, V> {
	private List<K> keys;
	private List<BPlusTreeNodeReference<K, V>> references;
	
	protected InnerBPlusTreeNode(BPlusTree<K, V> tree, BPlusTreeNodeReference<K, V> parentRefrence) {
		super(tree, parentRefrence);
		this.keys = new ArrayList<K>();
		this.references = new ArrayList<BPlusTreeNodeReference<K, V>>();
	}
	
	protected boolean isInner() {
		return true;
	}
	protected boolean isLeaf() {
		return false;
	}

	@Override
	protected AddResult add(K key, V value) throws BPlusTreeException {
		int keyIndex = getKeyIndex(key);
		K foundKey = keys.get(keyIndex);

		BPlusTreeNodeReference<K, V> reference = null;
		if (key.compareTo(foundKey) >= 0) {
			reference = references.get(++keyIndex);
		} else {
			reference = references.get(keyIndex);
		}
		
		BPlusTreeNode<K, V> node = reference.getNode();
		AddResult result = node.add(key, value);
		
		if (result != null) {
			this.keys.add(result.getKey());
			Collections.sort(this.keys);
			keyIndex = keys.indexOf(result.getKey());
			references.remove(reference);
			references.add(keyIndex, result.getLeftReference());
			result.getLeftReference().getNode().setParentReference(this.getThisReference());
			references.add(++keyIndex, result.getRightReference());
			result.getRightReference().getNode().setParentReference(this.getThisReference());

			this.getTree().addDirtyNodeReference(this.getThisReference());
			this.getTree().addDirtyNodeReference(result.getLeftReference());
			this.getTree().addDirtyNodeReference(result.getRightReference());

			if (keys.size() > this.getTree().getElementsPerNode()) {
				return this.split();
			}
		}
		
		return null;
	}

	@Override
	protected V get(K key) throws BPlusTreeException {
		try {
			int keyIndex = getKeyIndex(key);
			K foundKey = keys.get(keyIndex);
			if (key.compareTo(foundKey) < 0) {
				return this.getReferences().get(keyIndex).getNode().get(key);
			} else {
				return this.getReferences().get(++keyIndex).getNode().get(key);
			}
		} catch(IndexOutOfBoundsException e) {
			return null;
		}
	}

	private int getKeyIndex(K searchKey) throws BPlusTreeException {
		int index = -1;
		if (keys.size() > 0) {
			Iterator<K> it = keys.iterator();
			boolean found = false;
			while (it.hasNext() && !found) {
				K key = it.next();
				index++;
				found = key.compareTo(searchKey) >= 0;
			}
		} else {
			index = 0;
		}
		return index;
	}

	private AddResult split() throws BPlusTreeException {
		InnerBPlusTreeNode<K, V> leftNode = this;
		InnerBPlusTreeNode<K, V> rightNode = new InnerBPlusTreeNode<K, V>(this.getTree(), this.getParentReference());

		int middle = leftNode.getKeys().size() / 2;
		K middleKey = leftNode.getKeys().get(middle);
		
		for (int i = middle + 1; i < leftNode.getKeys().size(); i++) {
			rightNode.getKeys().add(leftNode.getKeys().get(i));
		}
		while (leftNode.getKeys().size() > middle) {
			leftNode.getKeys().remove(leftNode.getKeys().size() - 1);
		}

		BPlusTreeNodeReference<K, V> leftReference = leftNode.getThisReference();
		List<BPlusTreeNodeReference<K, V>> leftReferences = leftNode.getReferences();
		BPlusTreeNodeReference<K, V> rightReference = this.getTree().createReference();
		rightReference.setNode(rightNode);
		List<BPlusTreeNodeReference<K, V>> rightReferences = rightNode.getReferences();
		
		for (int i = middle + 1; i < leftReferences.size(); i++) {
			BPlusTreeNodeReference<K, V> reference = leftReferences.get(i);
			rightReferences.add(reference);
			reference.getNode().setParentReference(rightReference);
			tree.addDirtyNodeReference(reference);
		}
		while (leftReferences.size() > middle + 1) {
			leftReferences.remove(leftReferences.size() - 1);
		}

		tree.addDirtyNodeReference(leftReference);
		tree.addDirtyNodeReference(rightReference);
		tree.addDirtyNodeReference(parentReference);

		return new AddResult(middleKey, leftReference, rightReference);
	}
	
	protected List<BPlusTreeNodeReference<K, V>> getReferences() {
		return references;
	}
	protected void setReferences(List<BPlusTreeNodeReference<K, V>> references) {
		this.references = references;
	}

	protected List<K> getKeys() {
		return keys;
	}
	protected void setKeys(List<K> keys) {
		this.keys = keys;
	}

	@Override
	protected void validate() throws BPlusTreeException {
		List<K> keys = this.getKeys();

		if (keys.size() > this.getTree().getElementsPerNode()) {
			throw new BPlusTreeException("InnerNode: key list size is greater than maximun allowed");
		}
		
		for (int i = 1; i < keys.size(); i++) {
			K previousKey = keys.get(i - 1);
			K currentKey = keys.get(i);
			if (currentKey.compareTo(previousKey) < 0) {
				throw new BPlusTreeException("InnerNode: unordered key list");
			}
			if (currentKey.compareTo(previousKey) == 0) {
				throw new BPlusTreeException("InnerNode: duplicated entry in key list");
			}
		}
		
		List<BPlusTreeNodeReference<K, V>> references = this.getReferences();
		if (keys.size() + 1 != references.size()) {
			throw new BPlusTreeException("InnerNode: wrong size of references list");
		}

		for (int i = 0; i < keys.size(); i++) {
			K parentKey = keys.get(i);
			
			BPlusTreeNodeReference<K, V> leftReference = references.get(i); 
			BPlusTreeNode<K, V> leftChildNode = leftReference.getNode();
			this.validateLeftChild(parentKey, leftChildNode);
			leftChildNode.validate();
			
			BPlusTreeNodeReference<K, V> rightReference = references.get(i+1); 
			BPlusTreeNode<K, V> rightChildNode = rightReference.getNode();
			this.validateRightChild(parentKey, rightChildNode);
			rightChildNode.validate();
		}
	}

	protected void validateLeftChild(K parentKey, BPlusTreeNode<K, V> childNode) throws BPlusTreeException {
		this.validateChild(parentKey, childNode, true);
	}
	protected void validateRightChild(K parentKey, BPlusTreeNode<K, V> childNode) throws BPlusTreeException {
		this.validateChild(parentKey, childNode, false);
	}
	@SuppressWarnings("unchecked")
	private void validateChild(K parentKey, BPlusTreeNode<K, V> childNode, boolean isLeftChild) throws BPlusTreeException {
		Iterator<K> childKeysIterator = null;
		if(childNode instanceof InnerBPlusTreeNode)	{
			InnerBPlusTreeNode<K, V> innerNode = (InnerBPlusTreeNode<K, V>)childNode;
			childKeysIterator = innerNode.getKeys().iterator(); 
		} else if (childNode instanceof LeafBPlusTreeNode) {
			LeafBPlusTreeNode<K, V> leafNode = (LeafBPlusTreeNode<K, V>)childNode;
			childKeysIterator = leafNode.getData().keySet().iterator();
		}
		
		while (childKeysIterator.hasNext()) {
			K childKey = childKeysIterator.next();
			if (isLeftChild) {
				if (childKey.compareTo(parentKey) >= 0) {
					throw new BPlusTreeException("Error 1: all keys must be lower than parent key");
				}
			} else {
				if (childKey.compareTo(parentKey) < 0) {
					throw new BPlusTreeException("Error 2: all keys must be greater than parent key");
				}
			}
		}
	}
}
